package leetcode.tree;

import java.util.Stack;

/**
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 *
 * 假设一个二叉搜索树具有如下特征：
 *
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * @author MaoLin Wang
 * @date 2020/2/1414:10
 */
public class _98IsValidBST {
    public static boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        double inorder = - Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();

            if (root.val <= inorder) return false;
            inorder = root.val;
            root = root.right;
        }
        return true;


    }

    public static boolean isValidBST2(TreeNode root) {
        return isvalid(root,null,null);
    }

    private static boolean isvalid(TreeNode root,TreeNode left,TreeNode right) {
        if (root == null){
            return true;
        }
        if (left!=null && left.val>=root.val){
            return false;
        }
        if (right!=null && right.val<=root.val){
            return false;
        }
       return isvalid(root.left,left,root) && isvalid(root.right,root,right);
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left=new TreeNode(5);
        //root.left.left=new TreeNode(2);
       // root.left.left.left=new TreeNode(1);
       // root.left.right=new TreeNode(4);
        root.right=new TreeNode(15);
        root.right.left=new TreeNode(11);
        root.right.right=new TreeNode(20);
        boolean validBST = isValidBST(root);
        System.out.println(validBST);
    }
}
